// 6.56 试写一个算法，在先序后继线索二叉树中，查找给定结点*p在先序序列中的后继（假设二叉树的根结点未知）。并讨论实现此算法对存储结构有何要求？
/*
1.  ->rtag=Link 
	1.1   ->ltag==link   suc = ->left
	1.2   ->ltag==thrad  suc = ->right
2.  ->rtag=thread
	2.1  suc = ->right
*/

// 6.57 试写一个算法，在后序后继线索二叉树中，查找给定结点*p在后序序列中的后继（二叉树的根结点指针并未给出）。并讨论实现此算法对存储结构有何要求？

// 6.58 试写一个算法，在中序全线索二叉树的结点*p之下，插入一棵以结点*x为根、只有左子树的中序全线索二叉树，使*x为根的二叉树称为*p的左子树。若*p原来有左子树，则令它为*x的右子树。完成插入之后的二叉树应保持全线索化特性。
#include <stdio.h>
#include <stdlib.h>
typedef enum tag
{
	link,
	thread
};
typedef struct clue_T
{
	tag ltag;
	tag rtag;
	int data;
	struct clue_T *left;
	struct clue_T *right;
};
clue_T *pre;
// 1.mid clue 中序全线索化
void mid_enclue(clue_T *p)
{
	if (p)
	{
		if (p->ltag == link)
			mid_enclue(p->left);
		if (!p->left)
		{
			p->left = pre;
			p->ltag = thread;
		}
		if (!pre->right)
		{
			pre->right = p;
			pre->rtag = thread;
		}
		pre = p;
		if (p->rtag == link)
			mid_enclue(p->right);
	}
}
void pre_enclue(clue_T *p)
{
	if (p)
	{
		if (!p->left)
		{
			p->left = pre;
			p->ltag = thread;
		}
		if (!pre->right)
		{
			pre->right = p;
			pre->rtag = thread;
		}
		pre = p;
		if (p->ltag == link)
			pre_enclue(p->left);

		if (p->rtag == link)
			pre_enclue(p->right);
	}
}
void suc_enclue(clue_T *p)
{
	if (p)
	{
		if (p->ltag == link)
			suc_enclue(p->left);

		if (p->rtag == link)
			suc_enclue(p->right);
		if (!p->left)
		{
			p->left = pre;
			p->ltag = thread;
		}
		if (!pre->right)
		{
			pre->right = p;
			pre->rtag = thread;
		}
		pre = p;
	}
}

clue_T *enclue(clue_T *root, int selection)
{
	clue_T *h = (clue_T *)malloc(sizeof(clue_T));
	h->left = h->right = h;
	h->ltag = h->rtag = thread;
	if (root)
	{
		h->left = root;
		h->ltag = link;
		pre = h;
		switch (selection)
		{
		case 1:
			pre_enclue(root);
			break;
		case 2:
			mid_enclue(root);
			break;
		case 3:
			suc_enclue(root);
			break;
		default:
			break;
		}
		if (!pre->right)
		{
			pre->right = h;
			pre->rtag = thread;
		}
		h->right = pre;
	}
	return h;
}

void creat_tree(clue_T *&root, int a[], int len, int index)
{
	if (index < len)
	{
		if (a[index])
		{
			root = (clue_T *)malloc(sizeof(clue_T));
			root->data = a[index];
			root->right = root->left = NULL;
			root->ltag = root->rtag = link;
			creat_tree(root->left, a, len, 2 * index + 1);
			creat_tree(root->right, a, len, 2 * index + 2);
		}
		else
		{
			root = NULL;
		}
	}
}
// 6.56
// 此处和原题略微不同 此处有头结点
// 当无头结点时 结束标志是 root==NULL
clue_T *fun_6_56_1(clue_T *H, clue_T *root, int p)
{
	if (root && root != H)
	{
		if (root->data == p)
		{
			return root;
		}
		else
		{
			if (root->rtag == link)
			{
				if (root->ltag == link)
					return fun_6_56_1(H, root->left, p);
				else
					return fun_6_56_1(H, root->right, p);
			}
			else
			{
				return fun_6_56_1(H, root->right, p);
			}
		}
	}
}
void fun_6_56(clue_T *root, int p)
{
	clue_T *H = enclue(root, 1);
	clue_T *t = fun_6_56_1(H, root, p);
	printf("%3d", t->data);
}

// 6.57 mark
// need parent
void fun_6_57(clue_T *root, int p)
{
	clue_T *H = enclue(root, 1);
}

// 6.58
void fun_6_58(clue_T *&root, clue_T *&x)
{
	if (root->left)
	{
		x->right = root;
		x->rtag = link;
		clue_T *t = root->left;
		while (t->ltag == link)
		{
			t = t->left;
		}
		t->left = x;
		t->ltag = thread;
		root = x;
	}
	else
	{
		root->left = x;
		root->ltag = link;
		x->right = root;
		x->rtag = thread;
	}
}
int main()
{
	/*******************code*******************/
	int a[] = {1, 2, 3, 4, 5, NULL, 7, 8, NULL};
	clue_T *root;
	creat_tree(root, a, 9, 0);
	fun_6_56(root, 7);

	// 6.58
	int a2[] = {1, 2, 3};
	clue_T *p;
	creat_tree(p, a2, 3, 0);
	int a3[] = {4, 5, NULL, 6, NULL};
	clue_T *x;
	creat_tree(x, a3, 5, 0);
	enclue(p, 2);
	enclue(x, 2);
	// insert into node->data=1
	fun_6_58(p, x);
	/******************************************/
	printf("\n\n****************************\n");
	printf("Press Enter key to continue\n");
	getchar();
	return 0;
	/******************************************/
}
